<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>最短路径</title>
	<style>
		body{
			margin: 0;
			padding:0;
		}
		h2{
			display: inline-block;
		}
		.content{
			width: 850px;
			height: 700px;
			border: 1px solid #ccc;
			border-radius: 2%;
			margin:30px auto;
			background: #E6E1DB;
		}
		.content .box{
			padding:10px;
		}
		.content .box img{
			width: 830px;
			height: 420px;
		}
		.content .box .foo{
			margin-top: 10px;
		}
		#show{
			display: inline-block;
			width: 300px;
			height: 30px;
			text-align: center;
			line-height: 30px;
			margin-left: 50px;
			border: 1px solid #111723;
			border-radius: 6%;
			 word-spacing:5px;
		}
		.content .box .foo .details{
			margin:0 auto;
			width: 780px;
			height: 120px;
			padding: 20px;
			font-size: 20px;
			border: 1px solid #ccc;
		}
	</style>
</head>
<body>
	<div class="content">
		<div class="box">
			<img src="location.png" alt="">
			<div class="foo">
				<form action="post">
					<h2>请选择起始城市地址-->></h2>
					<select id="select">
						  <option value ="0">V0 - 波士顿</option>
						  <option value ="1">V1 - 纽约</option>
						  <option value="2">V2 - 芝加哥</option>
						  <option value="3">V3 - 丹佛</option>
						  <option value ="4">V4 - 亚特南大</option>
						  <option value ="5">V5 - 迈阿密</option>
						  <option value="6">V6 - 旧金山</option>
						  <option value="7">V7 - 洛杉矶</option>
					</select>
					<div id="show"></div>
				</form>
				<div class ="details">城市序列-->[波士顿,纽约,芝加哥,丹佛,亚特南大,迈阿密,旧金山,洛杉矶]<p>具体布局特效,城市之间显示细节就不做了,就酱!</p></div>
			</div>
		</div>
	</div>
<script>
//用于显示最短路径的div
  var showShort = document.getElementById('show');
  var details = document.querySelector(".details");
//最短路径算法Dijkstra 迪杰斯特拉
//用邻接矩阵存储一个图
//顶点
function Vertex(name) {
  this.name =name;
}
//邻接矩阵
//maxvex:顶点数
function arc(maxvex){
  this.maxvex = maxvex;
  this.arcnum = 0;
  this.data = new Array(maxvex);
  for (var i = 0; i < this.data.length; i++) {
    this.data[i] = new Array(maxvex);
    for (var j = 0; j < this.data[i].length; j++) {
      this.data[i][j] = Infinity;
      if(i==j){
        this.data[i][j] = 0;
      }
    }
  }
}
//图
function Mgraph(maxvex,vertexs){
  this.arc = new arc(maxvex);
  this.vertexs = vertexs;
}
//添加边,构造无向边
Mgraph.prototype.addArc = function(start,end,length){
  var i = this.vertexs.indexOf(start);
  var j = this.vertexs.indexOf(end);
  this.arc.data[i][j] = length;
  this.arc.data[j][i] = length;
  this.arc.arcnum++;
}
Mgraph.prototype.shortPath_Dijkstra = function(v0){
  var v0_index = this.vertexs.indexOf(v0);
  var final = [];//代表当前是否计算出来了结果
  var pathmatrix = [];//最短路径下标数组
  var shortpathtable = [];//存储到各点的最短路径的权值和
  console.info('开始初始化:准备计算'+v0.name+'到各个节点的最短路径');
  for (var i = 0; i < this.arc.maxvex; i++) {
    final.push(0);
    shortpathtable.push(this.arc.data[v0_index][i]);
    pathmatrix.push(0);
  }
  shortpathtable[v0_index] = 0;
  final[v0_index] = 1;
  console.info('初始化完毕:final:'+final);
  console.info('初始化完毕:pathmatrix:'+pathmatrix);
  console.info('初始化完毕:shortpathtable:'+shortpathtable);
  var min,k;
  for (var i = 0; i < this.arc.maxvex; i++) {
    //console.info('添加一个点:'+this.vertexs[i].name+'参与计算');
    if(i == v0_index){
      continue;
    }
    min = Infinity;
    for (var w = 0; w < this.arc.maxvex; w++) {
      /**
      以下的代码用于调试
      **/
      if(!final[w]&&shortpathtable[w]<Infinity){
        console.info('发现点:'+this.vertexs[w].name+'到'+v0.name+'的最短路径是'+
          shortpathtable[w]);
      }
      if(!final[w]&&shortpathtable[w]<min){
        k=w;
        min = shortpathtable[w];
      }
    }
    console.info(this.vertexs[k].name+'是最接近当前'+v0.name+'的');
    final[k] = 1;
    console.info('已经完成对点:'+this.vertexs[k].name+'最短路径计算');
    for (var w = 0; w < this.arc.maxvex; w++) {
      if(!final[w]&&(min+this.arc.data[k][w]<shortpathtable[w])){
        console.info('由于'+this.vertexs[k].name+'的参与,发现点:'
          +this.vertexs[w].name+'到'+v0.name+'的最短路径是'+
          (min+this.arc.data[k][w]));
        shortpathtable[w] = min+this.arc.data[k][w]
        pathmatrix[w] = k;
      }
    }
  }
  console.info(final);
  console.info(pathmatrix);
//打印出到达所有城市的最短路径
  showShort.innerHTML = shortpathtable;
}
//建造一个
var v0 = new Vertex('波士顿');
var v1 = new Vertex('纽约');
var v2 = new Vertex('芝加哥');
var v3 = new Vertex('丹佛');
var v4 = new Vertex('亚特南大');
var v5 = new Vertex('迈阿密');
var v6 = new Vertex('旧金山');
var v7 = new Vertex('洛杉矶');
var vertexs = [v0,v1,v2,v3,v4,v5,v6,v7];
var mgraph = new Mgraph(8,vertexs);
mgraph.addArc(v0,v2,79);//mgraph.addArc(v2,v0,79);
mgraph.addArc(v0,v1,39);//mgraph.addArc(v1,v0,39);
mgraph.addArc(v1,v5,99);//mgraph.addArc(v5,v1,99);
mgraph.addArc(v1,v2,59);//mgraph.addArc(v2,v1,59);
mgraph.addArc(v1,v7,129);//mgraph.addArc(v7,v1,129);
mgraph.addArc(v1,v4,79);//mgraph.addArc(v4,v1,79);
mgraph.addArc(v1,v6,129);//mgraph.addArc(v6,v1,129);
mgraph.addArc(v2,v4,99);//mgraph.addArc(v4,v2,99);
mgraph.addArc(v2,v3,69);//mgraph.addArc(v3,v2,69);
mgraph.addArc(v2,v6,99);//mgraph.addArc(v6,v2,99);
mgraph.addArc(v3,v7,89);//mgraph.addArc(v7,v3,89)
mgraph.addArc(v3,v6,89);//mgraph.addArc(v6,v3,89);
mgraph.addArc(v4,v5,69);//mgraph.addArc(v5,v4,69);
mgraph.addArc(v6,v7,39);//mgraph.addArc(v7,v6,39);
//console.info(mgraph.arc);
//以洛杉矶为起点,显示出到所有地点的最短路径
mgraph.shortPath_Dijkstra(v0);
var select = document.getElementById('select');
var index = select.selectedIndex;
var hasSelect = select.options[index].value;
select.onchange = function(){
        var values = this.value;
        if(values == 0){
        	mgraph.shortPath_Dijkstra(v0);
        }else if(values == 1){
        	mgraph.shortPath_Dijkstra(v1);
        }else if(values == 2){
        	mgraph.shortPath_Dijkstra(v2);
        }else if(values == 3){
        	mgraph.shortPath_Dijkstra(v3);
        }else if(values == 4){
        	mgraph.shortPath_Dijkstra(v4);
        }else if(values == 5){
        	mgraph.shortPath_Dijkstra(v5);
        }else if(values == 6){
        	mgraph.shortPath_Dijkstra(v6);
        }else{
        	mgraph.shortPath_Dijkstra(v7);
        }
  //       switch(values){
 	// case 0: mgraph.shortPath_Dijkstra(v0);break;
 	// case 1: mgraph.shortPath_Dijkstra(v1);break;
 	// case 2: mgraph.shortPath_Dijkstra(v2);break;
 	// case 3: mgraph.shortPath_Dijkstra(v3);break;
 	// case 4: mgraph.shortPath_Dijkstra(v4);break;
 	// case 5: mgraph.shortPath_Dijkstra(v5);break;
 	// case 6: mgraph.shortPath_Dijkstra(v6);break;
 	// case 7: mgraph.shortPath_Dijkstra(v7);break;
 	// }

 	//不想写了,哼
 	// for(var i=0;i<shortpathtable.length;i++){
 	// 	 details.innerHTML =  select.options[i].innerHTML + '-->' +  + '花费$' + shortpathtable[i];
 	// }
    }
</script>
</body>
</html>